import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LianBao
 * Date: 2025-03-02
 * Time: 20:09
 */
public class NQueen {

    boolean[] col;// 检查列是否有皇后
    boolean[] dig1;// 检查主对角线是否有皇后
    boolean[] dig2;// 检查副对角线是否有皇后
    List<List<String>> ret;// 返回结果
    char[][] path;//每一个可能的结果的棋盘
    int N;

    public List<List<String>> solveNQueens(int n) {
        col = new boolean[n];
        dig1 = new boolean[2 * n];
        dig2 = new boolean[2 * n];
        ret = new ArrayList<>();
        path = new char[n][n];
        N = n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                path[i][j] = '.';// 把棋盘都变成.
            }
        }
        dfs(0);
        return ret;
    }

    public void dfs(int line) {
        if (line == N) {
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }
        for (int column = 0; column < N; column++) {
            //剪枝
            if (!col[column] && !dig1[column - line + N] && !dig2[column + line]) {
                path[line][column] = 'Q';
                col[column] = true;
                dig1[column - line + N] = true;
                dig2[column + line] = true;
                dfs(line + 1);
                // 回溯
                path[line][column] = '.';
                col[column] = false;
                dig1[column - line + N] = false;
                dig2[column + line] = false;
            }
        }
    }

}
